import pygame
import tkinter
import tkinter.messagebox
import random
import time
import sys

sys.setrecursionlimit(5000) # 设置最大递归深度为3000

# 尺寸
window_size = (210, 210)
list_size = 21
# 颜色
black = (0, 0, 0)
white = (255, 255, 255)
red = (255, 0, 0)
green = (0, 255, 0)
blue = (0, 0, 255)

colour = [black, white, red, green, blue]

world_list = [[]]


# 递归分割算法
def recursive_segmentation(x1, y1, x2, y2):
    pass


Spar_list_i = []
Spar_list_j = []
route_stack = [[1,0]] # 线路图
route_history = [[0,0]] # 走过的点

def up(location):
    #横坐标为0，无法再向上走
    if location[1] == 1:
        return False
    else:
        new_location = [location[0], location[1]-1]
        #已经尝试过的点不会尝试第二次
        if new_location in route_history:
            return False
        #碰到墙不走
        elif world_list[new_location[0]][new_location[1]] == 5:
            return False
        else:
            route_stack.append(new_location)
            route_history.append(new_location)
            return True


def down(location):
    if location[1] == list_size - 2:
        return False
    else:
        new_location = [location[0], location[1] + 1]
        if new_location in route_history:
            return False
        elif world_list[new_location[0]][new_location[1]] == 5:
            return False
        else:
            route_stack.append(new_location)
            route_history.append(new_location)
            return True


def left(location):
    if location[0] == 1:
        return False
    else:
        new_location = [location[0] - 1, location[1]]
        if new_location in route_history:
            return False
        elif world_list[new_location[0]][new_location[1]] == 5:
            return False
        else:
            route_stack.append(new_location)
            route_history.append(new_location)
            return True


def right(location):
    if location[0] == list_size - 2:
        return False
    else:
        new_location = [location[0] + 1, location[1]]
        if new_location in route_history:
            return False
        elif world_list[new_location[0]][new_location[1]] == 5:
            return False
        else:
            route_stack.append(new_location)
            route_history.append(new_location)
            return True



# DFS 迷宫寻路
def DFS(si, sj, oi, oj):

    lo = [si, sj]
    while route_stack[-1] != [oi, oj]:
        if up(lo):
            lo = route_stack[-1]
            continue
        if down(lo):
            lo = route_stack[-1]
            continue
        if left(lo):
            lo = route_stack[-1]
            continue
        if right(lo):
            lo = route_stack[-1]
            continue
        route_stack.pop()
        lo = route_stack[-1]
    print(route_stack)




# 普利姆
def prim(i, j):
    #print('prim start')
    world_list[i][j] = 0
    if world_list[i - 1][j] == 1:
        Spar_list_i.append(i - 1)
        Spar_list_j.append(j)
        world_list[i - 1][j] = 3
    if world_list[i + 1][j] == 1:
        Spar_list_i.append(i + 1)
        Spar_list_j.append(j)
        world_list[i + 1][j] = 3
    if world_list[i][j - 1] == 1:
        Spar_list_i.append(i)
        Spar_list_j.append(j - 1)
        world_list[i][j - 1] = 3
    if world_list[i][j + 1] == 1:
        Spar_list_i.append(i)
        Spar_list_j.append(j + 1)
        world_list[i][j + 1] = 3
    #print(Spar_list_i)
    #print(Spar_list_j)
    while len(Spar_list_i) != 0:
        temp = random.randint(0, len(Spar_list_i) - 1)
        #print(temp)
        i = Spar_list_i[temp]
        j = Spar_list_j[temp]
        #print((i, j))
        if world_list[i - 1][j] + world_list[i + 1][j] == 0 or world_list[i][j - 1] + world_list[i][j + 1] == 0:
            world_list[i][j] = 5
            #print("del", end=' ')
            #print((Spar_list_i[temp], Spar_list_j[temp]))
            Spar_list_i.pop(temp)
            Spar_list_j.pop(temp)
        elif world_list[i - 1][j] + world_list[i + 1][j] == 2:
            world_list[i][j] = 0
            #print("del", end=' ')
            #print((Spar_list_i[temp], Spar_list_j[temp]))
            Spar_list_i.pop(temp)
            Spar_list_j.pop(temp)
            if world_list[i - 1][j] == 2:
                #print('prim in')
                prim(i - 1, j)
            elif world_list[i + 1][j] == 2:
                #print('prim in')
                prim(i + 1, j)
        elif world_list[i][j - 1] + world_list[i][j + 1] == 2:
            world_list[i][j] = 0
            #print("del", end=' ')
            #print((Spar_list_i[temp], Spar_list_j[temp]))
            Spar_list_i.pop(temp)
            Spar_list_j.pop(temp)
            if world_list[i][j - 1] == 2:
                #print('prim in')
                prim(i, j - 1)
            elif world_list[i][j + 1] == 2:
                #print('prim in')
                prim(i, j + 1)


# 画墙壁 1为樯 0为路
def show_room(screen):
    global list_size
    for i in range(list_size):
        for j in range(list_size):
            pygame.draw.rect(screen, colour[3], (0 * 10, 1 * 10, 10, 10), 0)
            pygame.draw.rect(screen, colour[4], ((list_size - 2) * 10, (list_size - 1) * 10, 10, 10), 0)
            if world_list[i][j] == 1 or world_list[i][j] == 3 or world_list[i][j] == 0 or world_list[i][j] == -1:
                show_wall(screen, j * 10, i * 10)
            if world_list[i][j] == -1:
                pass
                #pygame.draw.rect(screen, colour[1], (j * 10, i * 10, 10, 10), 0)
                #show_red(screen, j * 10, i * 10)

        for i in range(len(route_stack) - 2):
            pygame.draw.line(screen, colour[2], ((route_stack[i][1] * 10) + 5, (route_stack[i][0] * 10) + 5), ((route_stack[i + 1][1] * 10) + 5, (route_stack[i + 1][0] * 10) + 5), 2)
    pygame.draw.line(screen, colour[2], ((route_stack[-2][1] * 10) + 5, (route_stack[-2][0] * 10) + 5), (((list_size - 2) * 10) + 5, ((list_size - 2) * 10) + 5), 2)
    pygame.draw.line(screen, colour[2], (((list_size - 2) * 10) + 5, ((list_size - 2) * 10) + 5), (((list_size - 2) * 10) + 5, ((list_size - 1) * 10) + 5), 2)



# 初始化列表
def init_list():
    global list_size
    global world_list
    world_list = [[1 for i in range(list_size)] for i in range(list_size)]
    for i in range(list_size):
        for j in range(list_size):
            if i == 0:
                world_list[i][j] = 5
            if i == list_size - 1:
                world_list[i][j] = 5
            if j == 0:
                world_list[i][j] = 5
            if j == list_size - 1:
                world_list[i][j] = 5
            if i % 2 != 0 and j % 2 != 0:
                world_list[i][j] = 2
            if i % 2 == 0 and j % 2 == 0:
                world_list[i][j] = 5


def show_road():
    for i in route_stack:
        world_list[i[0]][i[1]] = -1

def first_show_list():
    for i in range(list_size):
        for j in range(list_size):
            print(world_list[i][j], end=' ')
        print()

# 打印列表
def show_list():
    global world_list
    global list_size
    for i in range(list_size):
        for j in range(list_size):
            print(world_list[i][j], end=' ')
        print()


# 画方块
def show_wall(screen, x, y):
    pygame.draw.rect(screen, colour[1], (x, y, 10, 10), 0)
# 画方块
def show_red(screen, x, y):
    pygame.draw.rect(screen, colour[2], (x + 2, y + 2, 5, 5), 0)

# 设置窗口大小
def size_init(x):
    global window_size
    global list_size
    try:
        x = int(x)
    except ValueError:
        print('输入的数据有误')
    if type(1) == type(x):
        window_size = (x, x)
        list_size = int(x / 10)


# 设置窗口大小的窗口
def init_window():
    top = tkinter.Tk()
    top.geometry("150x50+900+400")
    t1 = tkinter.StringVar()
    t1.set('输入大小（5的整数倍）')
    tkinter.Entry(top, textvariable=t1).pack()
    tkinter.Button(top, text="点我", command=lambda: size_init(t1.get())).pack()
    top.mainloop()


# 创建窗口
def maze_init():  # 初始化生成迷宫窗口
    global window_size
    pygame.init()
    screen = pygame.display.set_mode(window_size)
    pygame.display.set_caption('迷宫')
    running = True
    show_room(screen)
    while running:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                running = False

        pygame.display.update()
    pygame.quit()


if __name__ == "__main__":
    init_window()
    init_list()
    prim(1, 1)
    DFS(0, 1, list_size - 2, list_size - 2)
    show_road()
    first_show_list()
    show_list()
    maze_init()
